package sort;

import org.junit.Test;

import java.util.Arrays;

public class KthLargestElementInAnArray215 {

    @Test
    public void test() {
        findKthLargest(new int[]{3,2,1,5,6,4}, 2);
        findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4);
    }

    public int findKthLargest(int[] nums, int k) {
        int n = qsortAndReturnKth(nums, 0, nums.length-1, k);
        System.out.format("nums: %s, k: %d, n: %d\n", Arrays.toString(nums), k, n);
        return n;
    }

    // [startIndex, endIndex]
    public int partition(int[] nums, int startIndex, int endIndex) {
        int i = startIndex;
        int j = endIndex;
        int pivot = nums[i];

        while (i < j) {
            while (i < j && nums[j] <= pivot) {
                j--;
            }
            nums[i] = nums[j];
            while (i < j && pivot <= nums[i]) {
                i++;
            }
            nums[j] = nums[i];
        }
        // 这个赋值很关键
        nums[i] = pivot;
        return i;
    }

    public int qsortAndReturnKth(int[] nums, int startIndex, int endIndex, int k) {
        int partIndex = partition(nums, startIndex, endIndex);
        if (partIndex == k-1) {
            return nums[k-1];
        } else if (partIndex < k-1) {
            return qsortAndReturnKth(nums, partIndex+1, endIndex, k);
        } else {
            return qsortAndReturnKth(nums, startIndex, partIndex-1, k);
        }
    }
}
